package com.pan.alg.niuke.tree;

import java.util.*;

/**
 * 描述 请根据二叉树的前序遍历，中序遍历恢复二叉树，并打印出二叉树的右视图
 *
 * <p>数据范围： 0 \le n \le 100000≤n≤10000 要求： 空间复杂度 O(n)O(n)，时间复杂度 O(n)O(n)
 *
 * <p>如输入[1,2,4,5,3],[4,2,5,1,3]时，通过前序遍历的结果[1,2,4,5,3]和中序遍历的结果[4,2,5,1,3]可重建出以下二叉树：
 * 所以对应的输出为[1,3,5]。
 */
public class TreeSeeFromRight {

    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 求二叉树的右视图
     * @param qianxu int整型一维数组 先序遍历
     * @param zhongxu int整型一维数组 中序遍历
     * @return int整型一维数组
     */
    public int[] solve (int[] qianxu, int[] zhongxu) {
        // write code here

        //1、重建一棵二叉树
        TreeNode treeNode = reConstructBinaryTree(qianxu, zhongxu);

        //2、得到最右边节点
        List<TreeNode> rightNodes = getRightNodes(treeNode);

        //3、list转为数组
        int[] rights = new int[rightNodes.size()];
        for(int i = 0; i < rightNodes.size(); i++) {
            rights[i]=rightNodes.get(i).val;
        }

        return  rights;
    }

    public List<TreeNode> getRightNodes(TreeNode treeNode) {

        Queue<TreeNode> treeNodeQueue = new LinkedList<>();
        treeNodeQueue.add(treeNode);

        List<TreeNode> rightTreeNode = new ArrayList<>();
        while (!treeNodeQueue.isEmpty()){
            int size = treeNodeQueue.size();
            for(int i = 0; i < size; i++) {
                TreeNode pop = treeNodeQueue.poll();
                if(i==size-1){
                    rightTreeNode.add(pop);
                }
                if(pop.left!=null){
                    treeNodeQueue.add(pop.left);
                }
                if(pop.right!=null){
                    treeNodeQueue.add(pop.right);
                }
            }
        }
        return rightTreeNode;
    }


    public TreeNode reConstructBinaryTree(int [] pre,int [] vin) {

        int prel = pre.length;
        int vinl = vin.length;
        if(prel==0||vinl==0){
            return null;
        }

        TreeNode head = new TreeNode(pre[0]);

        for(int i=0;i<vinl;i++){

            if(pre[0]==vin[i]){

                //构建左子树
                head.left=reConstructBinaryTree(Arrays.copyOfRange(pre,1,i+1),Arrays.copyOfRange(vin,0,i));

                //构建右子树
                head.right=reConstructBinaryTree(Arrays.copyOfRange(pre,i+1,prel),Arrays.copyOfRange(vin,i+1,vinl));
                break;
            }
        }

        return head;
    }
}
